Dilworth 定理

一.一些定义

1.偏序集

若一个集合 AA , 满足一种关系 \le,且满足

  • 自反性: aA,aa\forall a \in A, a \le a
  • 反对称性: a,bA\forall a,b \in A,若 ab,baa \le b , b \le a ,则 a=ba=b
  • 传递性: a,b,cA\forall a,b,c \in A ,若 ab,bca \le b,b \le c , 则 aca \le c

那么 (A,)(A,\le) 为一个偏序集。

2.链,反链

AA 的一个子集中,如果每两个元素都是可比的,则称这个子集为链。

AA 的一个子集中,如果每两个元素都是不可比的,则称这个子集为反链。

二.Dilworth 定理

对于任意有限偏序集,其最大反链中元素的数目等于最小链划分中链的数目。

对于任意有限偏序集,其最长链中元素的数目等于其最小反链划分中反链的数目。

三.应用

1.最长不上升子序列

P1020 导弹拦截

求出一个序列的最长不上升子序列和至少被划分为多少个不上升子序列。

偏序关系 \le : i<ji < jaiaja_i \ge a_j

第一问最长链。

第二问求最小链划分,转换为最长反链 (i<ji < jai>aja_i > a_j) ,即最长下降子序列。

两问均可以 dp (nlogn)\mathcal(n \log n) 求得。

其余偏序关系同理。

2.图论

P4298 [CTSC2008]祭祀

将最长反链转换为最小链覆盖,然后用网络流求解。